package roaring

//
// Copyright (c) 2016 by the roaring authors.
// Licensed under the Apache License, Version 2.0.
//
// We derive a few lines of code from the sort.Search
// function in the golang standard library. That function
// is Copyright 2009 The Go Authors, and licensed
// under the following BSD-style license.
/*
Copyright (c) 2009 The Go Authors. All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

   * Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.
   * Redistributions in binary form must reproduce the above
copyright notice, this list of conditions and the following disclaimer
in the documentation and/or other materials provided with the
distribution.
   * Neither the name of Google Inc. nor the names of its
contributors may be used to endorse or promote products derived from
this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

import (
	
	
	
)

// runContainer16 does run-length encoding of sets of
// uint16 integers.
type runContainer16 struct {
	// iv is a slice of sorted, non-overlapping, non-adjacent intervals.
	iv []interval16
}

// interval16 is the internal to runContainer16
// structure that maintains the individual [start, last]
// closed intervals.
type interval16 struct {
	start  uint16
	length uint16 // length minus 1
}

func newInterval16Range(,  uint16) interval16 {
	if  <  {
		panic(fmt.Sprintf("last (%d) cannot be smaller than start (%d)", , ))
	}

	return interval16{
		,
		 - ,
	}
}

// runlen returns the count of integers in the interval.
func ( interval16) () int {
	return int(.length) + 1
}

func ( interval16) () uint16 {
	return .start + .length
}

// String produces a human viewable string of the contents.
func ( interval16) () string {
	return fmt.Sprintf("[%d, %d]", .start, .length)
}

func ivalString16( []interval16) string {
	var  string
	var  int
	var  interval16
	for ,  = range  {
		 += fmt.Sprintf("%v:[%d, %d], ", , .start, .last())
	}
	return 
}

// String produces a human viewable string of the contents.
func ( *runContainer16) () string {
	if len(.iv) == 0 {
		return "runContainer16{}"
	}
	 := ivalString16(.iv)
	return `runContainer16{` +  + `}`
}

// uint16Slice is a sort.Sort convenience method
type uint16Slice []uint16

// Len returns the length of p.
func ( uint16Slice) () int { return len() }

// Less returns p[i] < p[j]
func ( uint16Slice) (,  int) bool { return [] < [] }

// Swap swaps elements i and j.
func ( uint16Slice) (,  int) { [], [] = [], [] }

// addHelper helps build a runContainer16.
type addHelper16 struct {
	runstart      uint16
	runlen        uint16
	actuallyAdded uint16
	m             []interval16
	rc            *runContainer16
}

func ( *addHelper16) (,  uint16) {
	 := interval16{start: , length: }
	.m = append(.m, )
}

func ( *addHelper16) (,  uint16,  int) {
	if  == +1 {
		.runlen++
		.actuallyAdded++
	} else {
		if  <  {
			panic(fmt.Sprintf("newRunContainer16FromVals sees "+
				"unsorted vals; vals[%v]=cur=%v < prev=%v. Sort your vals"+
				" before calling us with alreadySorted == true.", , , ))
		}
		if  ==  {
			// ignore duplicates
		} else {
			.actuallyAdded++
			.storeIval(.runstart, .runlen)
			.runstart = 
			.runlen = 0
		}
	}
}

// newRunContainerRange makes a new container made of just the specified closed interval [rangestart,rangelast]
func newRunContainer16Range( uint16,  uint16) *runContainer16 {
	 := &runContainer16{}
	.iv = append(.iv, newInterval16Range(, ))
	return 
}

// newRunContainer16FromVals makes a new container from vals.
//
// For efficiency, vals should be sorted in ascending order.
// Ideally vals should not contain duplicates, but we detect and
// ignore them. If vals is already sorted in ascending order, then
// pass alreadySorted = true. Otherwise, for !alreadySorted,
// we will sort vals before creating a runContainer16 of them.
// We sort the original vals, so this will change what the
// caller sees in vals as a side effect.
func newRunContainer16FromVals( bool,  ...uint16) *runContainer16 {
	// keep this in sync with newRunContainer16FromArray below

	 := &runContainer16{}
	 := addHelper16{rc: }

	if ! {
		sort.Sort(uint16Slice())
	}
	 := len()
	var ,  uint16
	switch {
	case  == 0:
		// nothing more
	case  == 1:
		.m = append(.m, newInterval16Range([0], [0]))
		.actuallyAdded++
	default:
		.runstart = [0]
		.actuallyAdded++
		for  := 1;  < ; ++ {
			 = [-1]
			 = []
			.add(, , )
		}
		.storeIval(.runstart, .runlen)
	}
	.iv = .m
	return 
}

// newRunContainer16FromBitmapContainer makes a new run container from bc,
// somewhat efficiently. For reference, see the Java
// https://github.com/RoaringBitmap/RoaringBitmap/blob/master/src/main/java/org/roaringbitmap/RunContainer.java#L145-L192
func newRunContainer16FromBitmapContainer( *bitmapContainer) *runContainer16 {

	 := &runContainer16{}
	 := .numberOfRuns()
	if  == 0 {
		return 
	}
	.iv = make([]interval16, )

	 := 0            // index of current long in bitmap
	 := .bitmap[0] // its value
	 := 0
	for {
		// potentially multiword advance to first 1 bit
		for  == 0 &&  < len(.bitmap)-1 {
			++
			 = .bitmap[]
		}

		if  == 0 {
			// wrap up, no more runs
			return 
		}
		 := countTrailingZeros()
		 :=  + 64*
		// stuff 1s into number's LSBs
		 :=  | ( - 1)

		// find the next 0, potentially in a later word
		 := 0
		for  == maxWord &&  < len(.bitmap)-1 {
			++
			 = .bitmap[]
		}

		if  == maxWord {
			// a final unterminated run of 1s
			 = wordSizeInBits + *64
			.iv[].start = uint16()
			.iv[].length = uint16() - uint16() - 1
			return 
		}
		 := countTrailingZeros(^)
		 =  + *64
		.iv[].start = uint16()
		.iv[].length = uint16() - 1 - uint16()
		++
		// now, zero out everything right of runEnd.
		 =  & ( + 1)
		// We've lathered and rinsed, so repeat...
	}

}

// newRunContainer16FromArray populates a new
// runContainer16 from the contents of arr.
func newRunContainer16FromArray( *arrayContainer) *runContainer16 {
	// keep this in sync with newRunContainer16FromVals above

	 := &runContainer16{}
	 := addHelper16{rc: }

	 := .getCardinality()
	var ,  uint16
	switch {
	case  == 0:
		// nothing more
	case  == 1:
		.m = append(.m, newInterval16Range(.content[0], .content[0]))
		.actuallyAdded++
	default:
		.runstart = .content[0]
		.actuallyAdded++
		for  := 1;  < ; ++ {
			 = .content[-1]
			 = .content[]
			.add(, , )
		}
		.storeIval(.runstart, .runlen)
	}
	.iv = .m
	return 
}

// set adds the integers in vals to the set. Vals
// must be sorted in increasing order; if not, you should set
// alreadySorted to false, and we will sort them in place for you.
// (Be aware of this side effect -- it will affect the callers
// view of vals).
//
// If you have a small number of additions to an already
// big runContainer16, calling Add() may be faster.
func ( *runContainer16) ( bool,  ...uint16) {

	 := newRunContainer16FromVals(, ...)
	 := .union()
	.iv = .iv
}

// canMerge returns true iff the intervals
// a and b either overlap or they are
// contiguous and so can be merged into
// a single interval.
func canMerge16(,  interval16) bool {
	if int(.last())+1 < int(.start) {
		return false
	}
	return int(.last())+1 >= int(.start)
}

// haveOverlap differs from canMerge in that
// it tells you if the intersection of a
// and b would contain an element (otherwise
// it would be the empty set, and we return
// false).
func haveOverlap16(,  interval16) bool {
	if int(.last())+1 <= int(.start) {
		return false
	}
	return int(.last())+1 > int(.start)
}

// mergeInterval16s joins a and b into a
// new interval, and panics if it cannot.
func mergeInterval16s(,  interval16) ( interval16) {
	if !canMerge16(, ) {
		panic(fmt.Sprintf("cannot merge %#v and %#v", , ))
	}

	if .start < .start {
		.start = .start
	} else {
		.start = .start
	}

	if .last() > .last() {
		.length = .last() - .start
	} else {
		.length = .last() - .start
	}

	return
}

// intersectInterval16s returns the intersection
// of a and b. The isEmpty flag will be true if
// a and b were disjoint.
func intersectInterval16s(,  interval16) ( interval16,  bool) {
	if !haveOverlap16(, ) {
		 = true
		return
	}
	if .start > .start {
		.start = .start
	} else {
		.start = .start
	}

	 := .last()
	 := .last()
	var  uint16

	if  <  {
		 = 
	} else {
		 = 
	}
	.length =  - .start
	return
}

// union merges two runContainer16s, producing
// a new runContainer16 with the union of rc and b.
func ( *runContainer16) ( *runContainer16) *runContainer16 {

	// rc is also known as 'a' here, but golint insisted we
	// call it rc for consistency with the rest of the methods.

	var  []interval16

	 := int(len(.iv))
	 := int(len(.iv))

	var  int // next from a
	var  int // next from b

	// merged holds the current merge output, which might
	// get additional merges before being appended to m.
	var  interval16
	var  bool // is merged being used at the moment?

	var  interval16 // currently considering this interval16 from a
	var  interval16 // currently considering this interval16 from b

	 := 0
	for  <  &&  <  {
		++
		 = .iv[]
		 = .iv[]

		if  {
			 := false
			if canMerge16(, ) {
				 = mergeInterval16s(, )
				 = .indexOfIntervalAtOrAfter(int(.last())+1, +1)
				 = true
			}
			if canMerge16(, ) {
				 = mergeInterval16s(, )
				 = .indexOfIntervalAtOrAfter(int(.last())+1, +1)
				 = true
			}
			if ! {
				// we know that merged is disjoint from cura and curb
				 = append(, )
				 = false
			}
			continue

		} else {
			// !mergedUsed
			if !canMerge16(, ) {
				if .start < .start {
					 = append(, )
					++
				} else {
					 = append(, )
					++
				}
			} else {
				 = mergeInterval16s(, )
				 = true
				 = .indexOfIntervalAtOrAfter(int(.last())+1, +1)
				 = .indexOfIntervalAtOrAfter(int(.last())+1, +1)
			}
		}
	}
	var ,  bool
	if  >=  {
		 = true
	}
	if  >=  {
		 = true
	}
	// finish by merging anything remaining into merged we can:
	if  {
		if ! {
		:
			for  <  {
				 = .iv[]
				if canMerge16(, ) {
					 = mergeInterval16s(, )
					 = .indexOfIntervalAtOrAfter(int(.last())+1, +1)
				} else {
					break 
				}
			}

		}

		if ! {
		:
			for  <  {
				 = .iv[]
				if canMerge16(, ) {
					 = mergeInterval16s(, )
					 = .indexOfIntervalAtOrAfter(int(.last())+1, +1)
				} else {
					break 
				}
			}

		}

		 = append(, )
	}
	if  <  {
		 = append(, .iv[:]...)
	}
	if  <  {
		 = append(, .iv[:]...)
	}

	 := &runContainer16{iv: }
	return 
}

// unionCardinality returns the cardinality of the merger of two runContainer16s,  the union of rc and b.
func ( *runContainer16) ( *runContainer16) uint {

	// rc is also known as 'a' here, but golint insisted we
	// call it rc for consistency with the rest of the methods.
	 := uint(0)

	 := int(len(.iv))
	 := int(len(.iv))

	var  int // next from a
	var  int // next from b

	// merged holds the current merge output, which might
	// get additional merges before being appended to m.
	var  interval16
	var  bool // is merged being used at the moment?

	var  interval16 // currently considering this interval16 from a
	var  interval16 // currently considering this interval16 from b

	 := 0
	for  <  &&  <  {
		++
		 = .iv[]
		 = .iv[]

		if  {
			 := false
			if canMerge16(, ) {
				 = mergeInterval16s(, )
				 = .indexOfIntervalAtOrAfter(int(.last())+1, +1)
				 = true
			}
			if canMerge16(, ) {
				 = mergeInterval16s(, )
				 = .indexOfIntervalAtOrAfter(int(.last())+1, +1)
				 = true
			}
			if ! {
				// we know that merged is disjoint from cura and curb
				//m = append(m, merged)
				 += uint(.last()) - uint(.start) + 1
				 = false
			}
			continue

		} else {
			// !mergedUsed
			if !canMerge16(, ) {
				if .start < .start {
					 += uint(.last()) - uint(.start) + 1
					//m = append(m, cura)
					++
				} else {
					 += uint(.last()) - uint(.start) + 1
					//m = append(m, curb)
					++
				}
			} else {
				 = mergeInterval16s(, )
				 = true
				 = .indexOfIntervalAtOrAfter(int(.last())+1, +1)
				 = .indexOfIntervalAtOrAfter(int(.last())+1, +1)
			}
		}
	}
	var ,  bool
	if  >=  {
		 = true
	}
	if  >=  {
		 = true
	}
	// finish by merging anything remaining into merged we can:
	if  {
		if ! {
		:
			for  <  {
				 = .iv[]
				if canMerge16(, ) {
					 = mergeInterval16s(, )
					 = .indexOfIntervalAtOrAfter(int(.last())+1, +1)
				} else {
					break 
				}
			}

		}

		if ! {
		:
			for  <  {
				 = .iv[]
				if canMerge16(, ) {
					 = mergeInterval16s(, )
					 = .indexOfIntervalAtOrAfter(int(.last())+1, +1)
				} else {
					break 
				}
			}

		}

		//m = append(m, merged)
		 += uint(.last()) - uint(.start) + 1
	}
	for ,  := range .iv[:] {
		 += uint(.last()) - uint(.start) + 1
	}
	for ,  := range .iv[:] {
		 += uint(.last()) - uint(.start) + 1
	}
	return 
}

// indexOfIntervalAtOrAfter is a helper for union.
func ( *runContainer16) ( int,  int) int {
	, ,  := .searchRange(, , 0)
	if  {
		return 
	}
	return  + 1
}

// intersect returns a new runContainer16 holding the
// intersection of rc (also known as 'a')  and b.
func ( *runContainer16) ( *runContainer16) *runContainer16 {

	 := 
	 := int(len(.iv))
	 := int(len(.iv))
	 := &runContainer16{}
	if  == 0 ||  == 0 {
		return 
	}

	if  == 1 &&  == 1 {
		if !haveOverlap16(.iv[0], .iv[0]) {
			return 
		}
	}

	var  []interval16

	var  int
	var  int

	 := int(.iv[].start)
	 := int(.iv[].start)

	var  interval16
	var  int
	var , ,  bool
	var  bool
:
	for  <  &&  <  {

		, , , ,  =
			intersectWithLeftover16(, int(.iv[].last()), , int(.iv[].last()))

		if ! {
			switch {
			case  < :
				,  = .findNextIntervalThatIntersectsStartingFrom(+1, )
				if  {
					break 
				}
				 = int(.iv[].start)

			case  > :
				,  = .findNextIntervalThatIntersectsStartingFrom(+1, )
				if  {
					break 
				}
				 = int(.iv[].start)
			}

		} else {
			// isOverlap
			 = append(, )
			switch {
			case :
				// note that we change astart without advancing acuri,
				// since we need to capture any 2ndary intersections with a.iv[acuri]
				 = 
				++
				if  >=  {
					break 
				}
				 = int(.iv[].start)
			case :
				// note that we change bstart without advancing bcuri,
				// since we need to capture any 2ndary intersections with b.iv[bcuri]
				 = 
				++
				if  >=  {
					break 
				}
				 = int(.iv[].start)
			default:
				// neither had leftover, both completely consumed

				// advance to next a interval
				++
				if  >=  {
					break 
				}
				 = int(.iv[].start)

				// advance to next b interval
				++
				if  >=  {
					break 
				}
				 = int(.iv[].start)
			}
		}
	} // end for toploop

	if len() == 0 {
		return 
	}

	.iv = 
	return 
}

// intersectCardinality returns the cardinality of  the
// intersection of rc (also known as 'a')  and b.
func ( *runContainer16) ( *runContainer16) int {
	 := int(0)

	 := 
	 := int(len(.iv))
	 := int(len(.iv))
	if  == 0 ||  == 0 {
		return 0
	}

	if  == 1 &&  == 1 {
		if !haveOverlap16(.iv[0], .iv[0]) {
			return 0
		}
	}

	var  int
	var  int

	 := int(.iv[].start)
	 := int(.iv[].start)

	var  interval16
	var  int
	var , ,  bool
	var  bool
	 := 0
:
	for  <  &&  <  {
		++

		, , , ,  =
			intersectWithLeftover16(, int(.iv[].last()), , int(.iv[].last()))

		if ! {
			switch {
			case  < :
				,  = .findNextIntervalThatIntersectsStartingFrom(+1, )
				if  {
					break 
				}
				 = int(.iv[].start)

			case  > :
				,  = .findNextIntervalThatIntersectsStartingFrom(+1, )
				if  {
					break 
				}
				 = int(.iv[].start)
			}

		} else {
			// isOverlap
			 += int(.last()) - int(.start) + 1
			switch {
			case :
				// note that we change astart without advancing acuri,
				// since we need to capture any 2ndary intersections with a.iv[acuri]
				 = 
				++
				if  >=  {
					break 
				}
				 = int(.iv[].start)
			case :
				// note that we change bstart without advancing bcuri,
				// since we need to capture any 2ndary intersections with b.iv[bcuri]
				 = 
				++
				if  >=  {
					break 
				}
				 = int(.iv[].start)
			default:
				// neither had leftover, both completely consumed

				// advance to next a interval
				++
				if  >=  {
					break 
				}
				 = int(.iv[].start)

				// advance to next b interval
				++
				if  >=  {
					break 
				}
				 = int(.iv[].start)
			}
		}
	} // end for toploop

	return 
}

// get returns true iff key is in the container.
func ( *runContainer16) ( uint16) bool {
	, ,  := .search(int())
	return 
}

// numIntervals returns the count of intervals in the container.
func ( *runContainer16) () int {
	return len(.iv)
}

// searchRange returns alreadyPresent to indicate if the
// key is already in one of our interval16s.
//
// If key is alreadyPresent, then whichInterval16 tells
// you where.
//
// If key is not already present, then whichInterval16 is
// set as follows:
//
//	a) whichInterval16 == len(rc.iv)-1 if key is beyond our
//	   last interval16 in rc.iv;
//
//	b) whichInterval16 == -1 if key is before our first
//	   interval16 in rc.iv;
//
//	c) whichInterval16 is set to the minimum index of rc.iv
//	   which comes strictly before the key;
//	   so  rc.iv[whichInterval16].last < key,
//	   and  if whichInterval16+1 exists, then key < rc.iv[whichInterval16+1].start
//	   (Note that whichInterval16+1 won't exist when
//	   whichInterval16 is the last interval.)
//
// runContainer16.search always returns whichInterval16 < len(rc.iv).
//
// The search space is from startIndex to endxIndex. If endxIndex is set to zero, then there
// no upper bound.
func ( *runContainer16) ( int,  int,  int) ( int,  bool,  int) {
	 := int(len(.iv))
	if  == 0 {
		return -1, false, 0
	}
	if  == 0 {
		 = 
	}

	// sort.Search returns the smallest index i
	// in [0, n) at which f(i) is true, assuming that on the range [0, n),
	// f(i) == true implies f(i+1) == true.
	// If there is no such index, Search returns n.

	// For correctness, this began as verbatim snippet from
	// sort.Search in the Go standard lib.
	// We inline our comparison function for speed, and
	// annotate with numCompares
	// to observe and test that extra bounds are utilized.
	,  := , 
	for  <  {
		 :=  + (-)/2 // avoid overflow when computing h as the bisector
		// i <= h < j
		++
		if !( < int(.iv[].start)) {
			 =  + 1
		} else {
			 = 
		}
	}
	 := 
	// end std lib snippet.

	// The above is a simple in-lining and annotation of:
	/*	below := sort.Search(n,
		func(i int) bool {
			return key < rc.iv[i].start
		})
	*/
	 =  - 1

	if  ==  {
		// all falses => key is >= start of all interval16s
		// ... so does it belong to the last interval16?
		if  < int(.iv[-1].last())+1 {
			// yes, it belongs to the last interval16
			 = true
			return
		}
		// no, it is beyond the last interval16.
		// leave alreadyPreset = false
		return
	}

	// INVAR: key is below rc.iv[below]
	if  == 0 {
		// key is before the first first interval16.
		// leave alreadyPresent = false
		return
	}

	// INVAR: key is >= rc.iv[below-1].start and
	//        key is <  rc.iv[below].start

	// is key in below-1 interval16?
	if  >= int(.iv[-1].start) &&  < int(.iv[-1].last())+1 {
		// yes, it is. key is in below-1 interval16.
		 = true
		return
	}

	// INVAR: key >= rc.iv[below-1].endx && key < rc.iv[below].start
	// leave alreadyPresent = false
	return
}

// search returns alreadyPresent to indicate if the
// key is already in one of our interval16s.
//
// If key is alreadyPresent, then whichInterval16 tells
// you where.
//
// If key is not already present, then whichInterval16 is
// set as follows:
//
//	a) whichInterval16 == len(rc.iv)-1 if key is beyond our
//	   last interval16 in rc.iv;
//
//	b) whichInterval16 == -1 if key is before our first
//	   interval16 in rc.iv;
//
//	c) whichInterval16 is set to the minimum index of rc.iv
//	   which comes strictly before the key;
//	   so  rc.iv[whichInterval16].last < key,
//	   and  if whichInterval16+1 exists, then key < rc.iv[whichInterval16+1].start
//	   (Note that whichInterval16+1 won't exist when
//	   whichInterval16 is the last interval.)
//
// runContainer16.search always returns whichInterval16 < len(rc.iv).
func ( *runContainer16) ( int) ( int,  bool,  int) {
	return .searchRange(, 0, 0)
}

// getCardinality returns the count of the integers stored in the
// runContainer16. The running complexity depends on the size
// of the container.
func ( *runContainer16) () int {
	// have to compute it
	 := 0
	for ,  := range .iv {
		 += .runlen()
	}
	return 
}

// isEmpty returns true if the container is empty.
// It runs in constant time.
func ( *runContainer16) () bool {
	return len(.iv) == 0
}

// AsSlice decompresses the contents into a []uint16 slice.
func ( *runContainer16) () []uint16 {
	 := make([]uint16, .getCardinality())
	 := 0
	for ,  := range .iv {
		for  := .start;  <= .last(); ++ {
			[] = 
			++
		}
	}
	return 
}

// newRunContainer16 creates an empty run container.
func newRunContainer16() *runContainer16 {
	return &runContainer16{}
}

// newRunContainer16CopyIv creates a run container, initializing
// with a copy of the supplied iv slice.
func newRunContainer16CopyIv( []interval16) *runContainer16 {
	 := &runContainer16{
		iv: make([]interval16, len()),
	}
	copy(.iv, )
	return 
}

func ( *runContainer16) () *runContainer16 {
	 := newRunContainer16CopyIv(.iv)
	return 
}

// newRunContainer16TakeOwnership returns a new runContainer16
// backed by the provided iv slice, which we will
// assume exclusive control over from now on.
func newRunContainer16TakeOwnership( []interval16) *runContainer16 {
	 := &runContainer16{
		iv: ,
	}
	return 
}

const baseRc16Size = int(unsafe.Sizeof(runContainer16{}))
const perIntervalRc16Size = int(unsafe.Sizeof(interval16{}))

const baseDiskRc16Size = int(unsafe.Sizeof(uint16(0)))

// see also runContainer16SerializedSizeInBytes(numRuns int) int

// getSizeInBytes returns the number of bytes of memory
// required by this runContainer16.
func ( *runContainer16) () int {
	return perIntervalRc16Size*len(.iv) + baseRc16Size
}

// runContainer16SerializedSizeInBytes returns the number of bytes of disk
// required to hold numRuns in a runContainer16.
func runContainer16SerializedSizeInBytes( int) int {
	return perIntervalRc16Size* + baseDiskRc16Size
}

// Add adds a single value k to the set.
func ( *runContainer16) ( uint16) ( bool) {
	// TODO comment from runContainer16.java:
	// it might be better and simpler to do return
	// toBitmapOrArrayContainer(getCardinality()).add(k)
	// but note that some unit tests use this method to build up test
	// runcontainers without calling runOptimize

	 := int()

	, ,  := .search()
	if  {
		return // already there
	}
	 = true

	 := int(len(.iv))
	if  == -1 {
		// we may need to extend the first run
		if  > 0 {
			if .iv[0].start == +1 {
				.iv[0].start = 
				.iv[0].length++
				return
			}
		}
		// nope, k stands alone, starting the new first interval16.
		.iv = append([]interval16{newInterval16Range(, )}, .iv...)
		return
	}

	// are we off the end? handle both index == n and index == n-1:
	if  >= -1 {
		if int(.iv[-1].last())+1 ==  {
			.iv[-1].length++
			return
		}
		.iv = append(.iv, newInterval16Range(, ))
		return
	}

	// INVAR: index and index+1 both exist, and k goes between them.
	//
	// Now: add k into the middle,
	// possibly fusing with index or index+1 interval16
	// and possibly resulting in fusing of two interval16s
	// that had a one integer gap.

	 := 
	 :=  + 1

	// are we fusing left and right by adding k?
	if int(.iv[].last())+1 ==  && int(.iv[].start) == +1 {
		// fuse into left
		.iv[].length = .iv[].last() - .iv[].start
		// remove redundant right
		.iv = append(.iv[:+1], .iv[+1:]...)
		return
	}

	// are we an addition to left?
	if int(.iv[].last())+1 ==  {
		// yes
		.iv[].length++
		return
	}

	// are we an addition to right?
	if int(.iv[].start) == +1 {
		// yes
		.iv[].start = 
		.iv[].length++
		return
	}

	// k makes a standalone new interval16, inserted in the middle
	 := append([]interval16{newInterval16Range(, )}, .iv[:]...)
	.iv = append(.iv[:+1], ...)
	return
}

// runIterator16 advice: you must call hasNext()
// before calling next()/peekNext() to insure there are contents.
type runIterator16 struct {
	rc            *runContainer16
	curIndex      int
	curPosInIndex uint16
}

// newRunIterator16 returns a new empty run container.
func ( *runContainer16) () *runIterator16 {
	return &runIterator16{rc: , curIndex: 0, curPosInIndex: 0}
}

func ( *runContainer16) ( func( uint16) bool) bool {
	 := runIterator16{, 0, 0}

	for .hasNext() {
		if !(.next()) {
			return false
		}
	}

	return true
}

// hasNext returns false if calling next will panic. It
// returns true when there is at least one more value
// available in the iteration sequence.
func ( *runIterator16) () bool {
	return int(len(.rc.iv)) > .curIndex+1 ||
		(int(len(.rc.iv)) == .curIndex+1 && .rc.iv[.curIndex].length >= .curPosInIndex)
}

// next returns the next value in the iteration sequence.
func ( *runIterator16) () uint16 {
	 := .rc.iv[.curIndex].start + .curPosInIndex

	if .curPosInIndex == .rc.iv[.curIndex].length {
		.curPosInIndex = 0
		.curIndex++
	} else {
		.curPosInIndex++
	}

	return 
}

// peekNext returns the next value in the iteration sequence without advancing the iterator
func ( *runIterator16) () uint16 {
	return .rc.iv[.curIndex].start + .curPosInIndex
}

// advanceIfNeeded advances as long as the next value is smaller than minval
func ( *runIterator16) ( uint16) {
	if !.hasNext() || .peekNext() >=  {
		return
	}

	// interval cannot be -1 because of minval > peekNext
	, ,  := .rc.searchRange(int(), .curIndex, int(len(.rc.iv)))

	// if the minval is present, set the curPosIndex at the right position
	if  {
		.curIndex = 
		.curPosInIndex =  - .rc.iv[.curIndex].start
	} else {
		// otherwise interval is set to to the minimum index of rc.iv
		// which comes strictly before the key, that's why we set the next interval
		.curIndex =  + 1
		.curPosInIndex = 0
	}
}

// runReverseIterator16 advice: you must call hasNext()
// before calling next() to insure there are contents.
type runReverseIterator16 struct {
	rc            *runContainer16
	curIndex      int    // index into rc.iv
	curPosInIndex uint16 // offset in rc.iv[curIndex]
}

// newRunReverseIterator16 returns a new empty run iterator.
func ( *runContainer16) () *runReverseIterator16 {
	 := int(len(.iv)) - 1
	 := uint16(0)

	if  >= 0 {
		 = .iv[].length
	}

	return &runReverseIterator16{
		rc:            ,
		curIndex:      ,
		curPosInIndex: ,
	}
}

// hasNext returns false if calling next will panic. It
// returns true when there is at least one more value
// available in the iteration sequence.
func ( *runReverseIterator16) () bool {
	return .curIndex > 0 || .curIndex == 0 && .curPosInIndex >= 0
}

// next returns the next value in the iteration sequence.
func ( *runReverseIterator16) () uint16 {
	 := .rc.iv[.curIndex].start + .curPosInIndex

	if .curPosInIndex > 0 {
		.curPosInIndex--
	} else {
		.curIndex--

		if .curIndex >= 0 {
			.curPosInIndex = .rc.iv[.curIndex].length
		}
	}

	return 
}

func ( *runContainer16) () *runIterator16 {
	return .newRunIterator16()
}

// hs are the high bits to include to avoid needing to reiterate over the buffer in NextMany
func ( *runIterator16) ( uint32,  []uint32) int {
	 := 0

	if !.hasNext() {
		return 
	}

	// start and end are inclusive
	for  < len() {
		 := 0

		if .rc.iv[.curIndex].length >= .curPosInIndex {
			// add as many as you can from this seq
			 = minOfInt(int(.rc.iv[.curIndex].length-.curPosInIndex)+1, len()-)
			 := uint32(.rc.iv[.curIndex].start+.curPosInIndex) | 

			// allows BCE
			 := [ : +]
			for  := range  {
				[] =  + uint32()
			}

			// update values
			 += 
		}

		if +int(.curPosInIndex) > int(.rc.iv[.curIndex].length) {
			.curPosInIndex = 0
			.curIndex++

			if .curIndex == int(len(.rc.iv)) {
				break
			}
		} else {
			.curPosInIndex += uint16() //moreVals always fits in uint16
		}
	}

	return 
}

func ( *runIterator16) ( uint64,  []uint64) int {
	 := 0

	if !.hasNext() {
		return 
	}

	// start and end are inclusive
	for  < len() {
		 := 0

		if .rc.iv[.curIndex].length >= .curPosInIndex {
			// add as many as you can from this seq
			 = minOfInt(int(.rc.iv[.curIndex].length-.curPosInIndex)+1, len()-)
			 := uint64(.rc.iv[.curIndex].start+.curPosInIndex) | 

			// allows BCE
			 := [ : +]
			for  := range  {
				[] =  + uint64()
			}

			// update values
			 += 
		}

		if +int(.curPosInIndex) > int(.rc.iv[.curIndex].length) {
			.curPosInIndex = 0
			.curIndex++

			if .curIndex == int(len(.rc.iv)) {
				break
			}
		} else {
			.curPosInIndex += uint16() //moreVals always fits in uint16
		}
	}

	return 
}

// remove removes key from the container.
func ( *runContainer16) ( uint16) ( bool) {

	var  int
	, , _ = .search(int())
	if ! {
		return // already removed, nothing to do.
	}
	 :=  - .iv[].start
	.deleteAt(&, &)
	return
}

// internal helper functions

func ( *runContainer16) ( *int,  *uint16) {
	 := *
	 := *

	// are we first, last, or in the middle of our interval16?
	switch {
	case  == 0:
		if int(.iv[].length) == 0 {
			// our interval disappears
			.iv = append(.iv[:], .iv[+1:]...)
			// curIndex stays the same, since the delete did
			// the advance for us.
			* = 0
		} else {
			.iv[].start++ // no longer overflowable
			.iv[].length--
		}
	case  == .iv[].length:
		// length
		.iv[].length--
		// our interval16 cannot disappear, else we would have been pos == 0, case first above.
		*--
		// if we leave *curIndex alone, then Next() will work properly even after the delete.
	default:
		//middle
		// split into two, adding an interval16
		 := newInterval16Range(.iv[].start, .iv[].start+*-1)

		 := int(.iv[].start+*) + 1
		if  > int(MaxUint16) {
			panic("overflow?!?!")
		}
		 := newInterval16Range(uint16(), .iv[].last())
		 := append([]interval16{, }, .iv[+1:]...)
		.iv = append(.iv[:], ...)
		// update curIndex and curPosInIndex
		*++
		* = 0
	}

}

func have4Overlap16(, , ,  int) bool {
	if +1 <=  {
		return false
	}
	return +1 > 
}

func intersectWithLeftover16(, , ,  int) (, ,  bool,  int,  interval16) {
	if !have4Overlap16(, , , ) {
		return
	}
	 = true

	// do the intersection:
	if  >  {
		.start = uint16()
	} else {
		.start = uint16()
	}

	switch {
	case  < :
		 = true
		 =  + 1
		.length = uint16() - .start
	case  < :
		 = true
		 =  + 1
		.length = uint16() - .start
	default:
		// alast == blast
		.length = uint16() - .start
	}

	return
}

func ( *runContainer16) ( int,  int) ( int,  bool) {
	, ,  := .searchRange(, , 0)
	// rc.search always returns w < len(rc.iv)
	if  <  {
		// not found and comes before lower bound startIndex,
		// so just use the lower bound.
		if  == int(len(.iv)) {
			// also this bump up means that we are done
			return , true
		}
		return , false
	}

	return , false
}

func sliceToString16( []interval16) string {
	 := ""
	for  := range  {
		 += fmt.Sprintf("%v: %s, ", , [])
	}
	return 
}

// helper for invert
func ( *runContainer16) ( uint16,  int) []interval16 {
	 := .iv[]
	if .last() == MaxUint16 {
		if .start ==  {
			return nil // empty container
		}
		return []interval16{newInterval16Range(, .start-1)}
	}
	if .start ==  {
		return []interval16{newInterval16Range(.last()+1, MaxUint16)}
	}
	// invert splits
	return []interval16{
		newInterval16Range(, .start-1),
		newInterval16Range(.last()+1, MaxUint16),
	}
}

// invert returns a new container (not inplace), that is
// the inversion of rc. For each bit b in rc, the
// returned value has !b
func ( *runContainer16) () *runContainer16 {
	 := len(.iv)
	var  []interval16
	switch  {
	case 0:
		return &runContainer16{iv: []interval16{newInterval16Range(0, MaxUint16)}}
	case 1:
		return &runContainer16{iv: .invertlastInterval(0, 0)}
	}
	var  int
	 :=  - 1
	for ,  := range .iv {
		if  ==  {
			// invertlastInteval will add both intervals (b) and (c) in
			// diagram below.
			 = append(, .invertlastInterval(uint16(), )...)
			break
		}
		// INVAR: i and cur are not the last interval, there is a next at i+1
		//
		// ........[cur.start, cur.last] ...... [next.start, next.last]....
		//    ^                             ^                           ^
		//   (a)                           (b)                         (c)
		//
		// Now: we add interval (a); but if (a) is empty, for cur.start==0, we skip it.
		if .start > 0 {
			 = append(, newInterval16Range(uint16(), .start-1))
		}
		 = int(.last() + 1)
	}
	return &runContainer16{iv: }
}

func ( interval16) ( interval16) bool {
	return .start == .start && .length == .length
}

func ( interval16) ( interval16) bool {
	return .start <= .start && .last() <= .last()
}

func ( interval16) ( interval16) ( []interval16,  int) {
	,  := intersectInterval16s(, )

	if  {
		return nil, 0
	}
	if .isSuperSetOf() {
		return nil, .runlen()
	}

	switch {
	case .start > .start && .last() < .last():
		 := newInterval16Range(.start, .start-1)
		 := newInterval16Range(.last()+1, .last())
		return []interval16{, }, .runlen()
	case .start == .start:
		return []interval16{newInterval16Range(.last()+1, .last())}, .runlen()
	default:
		return []interval16{newInterval16Range(.start, .start-1)}, .runlen()
	}
}

func ( *runContainer16) ( interval16) {
	 := make([]interval16, len(.iv))
	copy(, .iv)
	 := int(len(.iv))
	if  == 0 {
		return // already done.
	}

	,  := intersectInterval16s(newInterval16Range(.iv[0].start, .iv[-1].last()), )
	if  {
		return // done
	}

	// INVAR there is some intersection between rc and del
	, ,  := .search(int(.start))
	, ,  := .search(int(.last()))
	if  == -1 {
		if  == -1 && ! {
			.iv = nil
			return
		}
	}
	// some intervals will remain
	switch {
	case  && :
		,  := .iv[].subtractInterval()

		// would overwrite values in iv b/c res0 can have len 2. so
		// write to origiv instead.
		 := 1 +  - 
		 := int(len()) - 
		 := int(len(.iv)) + 

		//	rc.iv = append(pre, caboose...)
		//	return

		if  !=  {
			,  := .iv[].subtractInterval()
			 = append(, ...)
			 = int(len()) - 
			 = int(len(.iv)) + 
		}
		switch {
		case  < 0:
			// shrink
			copy(.iv[+int(len()):], .iv[+1:])
			copy(.iv[:+int(len())], )
			.iv = .iv[:]
			return
		case  == 0:
			// stay the same
			copy(.iv[:+int(len())], )
			return
		default:
			// changeSize > 0 is only possible when ilast == istart.
			// Hence we now know: changeSize == 1 and len(res0) == 2
			.iv = append(.iv, interval16{})
			// len(rc.iv) is correct now, no need to rc.iv = rc.iv[:newSize]

			// copy the tail into place
			copy(.iv[+2:], .iv[+1:])
			// copy the new item(s) into place
			copy(.iv[:+2], )
			return
		}

	case ! && !:
		// we get to discard whole intervals

		// from the search() definition:

		// if del.start is not present, then istart is
		// set as follows:
		//
		//  a) istart == n-1 if del.start is beyond our
		//     last interval16 in rc.iv;
		//
		//  b) istart == -1 if del.start is before our first
		//     interval16 in rc.iv;
		//
		//  c) istart is set to the minimum index of rc.iv
		//     which comes strictly before the del.start;
		//     so  del.start > rc.iv[istart].last,
		//     and  if istart+1 exists, then del.start < rc.iv[istart+1].startx

		// if del.last is not present, then ilast is
		// set as follows:
		//
		//  a) ilast == n-1 if del.last is beyond our
		//     last interval16 in rc.iv;
		//
		//  b) ilast == -1 if del.last is before our first
		//     interval16 in rc.iv;
		//
		//  c) ilast is set to the minimum index of rc.iv
		//     which comes strictly before the del.last;
		//     so  del.last > rc.iv[ilast].last,
		//     and  if ilast+1 exists, then del.last < rc.iv[ilast+1].start

		// INVAR: istart >= 0
		 := .iv[:+1]
		if  == -1 {
			.iv = 
			return
		}
		// INVAR: ilast < n-1
		 :=  - 
		 := -
		 := int(len(.iv)) + 
		if  != 0 {
			copy(.iv[+1+:], .iv[+1:])
		}
		.iv = .iv[:]
		return

	case  && !:
		// we can only shrink or stay the same size
		// i.e. we either eliminate the whole interval,
		// or just cut off the right side.
		,  := .iv[].subtractInterval()
		if len() > 0 {
			// len(res) must be 1
			.iv[] = [0]
		}
		 := 1 + ( - )
		 := int(len()) - 
		 := int(len(.iv)) + 
		if  != 0 {
			copy(.iv[+1+:], .iv[+1:])
		}
		.iv = .iv[:]
		return

	case ! && :
		// we can only shrink or stay the same size
		,  := .iv[].subtractInterval()
		 :=  - 
		 := int(len()) - 
		 := int(len(.iv)) + 
		if  != 0 {
			// move the tail first to make room for res1
			copy(.iv[+1+:], .iv[+1:])
		}
		copy(.iv[+1:], )
		.iv = .iv[:]
		return
	}
}

// compute rc minus b, and return the result as a new value (not inplace).
// port of run_container_andnot from CRoaring...
// https://github.com/RoaringBitmap/CRoaring/blob/master/src/containers/run.c#L435-L496
func ( *runContainer16) ( *runContainer16) *runContainer16 {

	if len(.iv) == 0 || len(.iv) == 0 {
		return 
	}

	 := newRunContainer16()
	 := 0
	 := 0

	 := 

	 := .iv[].start
	 := .iv[].last()
	 := .iv[].start
	 := .iv[].last()

	 := len(.iv)
	 := len(.iv)

	for  <  &&  <  {
		switch {
		case  < :
			// output the first run
			.iv = append(.iv, newInterval16Range(, ))
			++
			if  <  {
				 = .iv[].start
				 = .iv[].last()
			}
		case  < :
			// exit the second run
			++
			if  <  {
				 = .iv[].start
				 = .iv[].last()
			}
		default:
			//   a: [             ]
			//   b:            [    ]
			// alast >= bstart
			// blast >= astart
			if  <  {
				.iv = append(.iv, newInterval16Range(, -1))
			}
			if  >  {
				 =  + 1
			} else {
				++
				if  <  {
					 = .iv[].start
					 = .iv[].last()
				}
			}
		}
	}
	if  <  {
		.iv = append(.iv, newInterval16Range(, ))
		++
		if  <  {
			.iv = append(.iv, .iv[:]...)
		}
	}

	return 
}

func ( *runContainer16) () ( int) {
	return len(.iv)
}

func ( *runContainer16) () contype {
	return run16Contype
}

func ( *runContainer16) ( *runContainer16) bool {
	// Check if the containers are the same object.
	if  ==  {
		return true
	}

	if len(.iv) != len(.iv) {
		return false
	}

	for ,  := range .iv {
		if  != .iv[] {
			return false
		}
	}
	return true
}

// compile time verify we meet interface requirements
var _ container = &runContainer16{}

func ( *runContainer16) () container {
	return newRunContainer16CopyIv(.iv)
}

func ( *runContainer16) () uint16 {
	return .iv[0].start // assume not empty
}

func ( *runContainer16) () uint16 {
	return .iv[len(.iv)-1].last() // assume not empty
}

func ( *runContainer16) () bool {
	return (len(.iv) == 1) && ((.iv[0].start == 0) && (.iv[0].last() == MaxUint16))
}

func ( *runContainer16) ( container) container {
	if .isFull() {
		return .clone()
	}
	switch c := .(type) {
	case *runContainer16:
		return .intersect()
	case *arrayContainer:
		return .andArray()
	case *bitmapContainer:
		return .andBitmapContainer()
	}
	panic("unsupported container type")
}

func ( *runContainer16) ( container) int {
	switch c := .(type) {
	case *runContainer16:
		return int(.intersectCardinality())
	case *arrayContainer:
		return .andArrayCardinality()
	case *bitmapContainer:
		return .andBitmapContainerCardinality()
	}
	panic("unsupported container type")
}

// andBitmapContainer finds the intersection of rc and b.
func ( *runContainer16) ( *bitmapContainer) container {
	 := newBitmapContainerFromRun()
	return .andBitmap()
}

func ( *runContainer16) ( *arrayContainer) int {
	 := 0
	 := 0
	 := .getCardinality()
	if  == 0 {
		return 0 // won't happen in actual code
	}
	 := .content[]
:
	for ,  := range .iv {
		for  < .start {
			++
			if  ==  {
				break 
			}
			 = .content[]
		}
		for  <= .last() {
			++
			++
			if  ==  {
				break 
			}
			 = .content[]
		}
	}
	return 
}

func ( *runContainer16) ( container) container {
	if .isFull() {
		return .clone()
	}
	switch c := .(type) {
	case *runContainer16:
		return .inplaceIntersect()
	case *arrayContainer:
		return .andArray()
	case *bitmapContainer:
		return .iandBitmapContainer()
	}
	panic("unsupported container type")
}

func ( *runContainer16) ( *runContainer16) container {
	 := .intersect()
	* = *
	return 
}

func ( *runContainer16) ( *bitmapContainer) container {
	 := .andBitmapContainer()
	* = *newRunContainer16FromContainer()
	return 
}

func ( *runContainer16) ( *arrayContainer) container {
	if len(.iv) == 0 {
		return newArrayContainer()
	}

	 := .getCardinality()
	 := newArrayContainerCapacity()

	for ,  := 0, 0;  < ; {
		 := .iv[]
		 := .content[]

		for .last() <  {
			++
			if  == len(.iv) {
				return 
			}
			 = .iv[]
		}

		if .start >  {
			 = advanceUntil(.content, , len(.content), .start)
		} else {
			.content = append(.content, )
			++
		}
	}
	return 
}

func ( *runContainer16) ( container) container {
	switch c := .(type) {
	case *arrayContainer:
		return .andNotArray()
	case *bitmapContainer:
		return .andNotBitmap()
	case *runContainer16:
		return .andNotRunContainer16()
	}
	panic("unsupported container type")
}

func ( *runContainer16) ( []uint32,  int,  uint32) int {
	 := 
	var  int
	for ,  := range .iv {
		 := .runlen()
		for  := int(0);  < ; ++ {
			 = int(.start) + 
			[] = uint32() | 
			++
		}
	}
	return 
}

func ( *runContainer16) () shortPeekable {
	return .newRunIterator16()
}

func ( *runContainer16) () shortIterable {
	return .newRunReverseIterator16()
}

func ( *runContainer16) () manyIterable {
	return .newManyRunIterator16()
}

// add the values in the range [firstOfRange, endx). endx
// is still abe to express 2^16 because it is an int not an uint16.
func ( *runContainer16) (,  int) container {

	if  >  {
		panic(fmt.Sprintf("invalid %v = endx > firstOfRange", ))
	}
	if  ==  {
		return 
	}
	 := newRunContainer16TakeOwnership([]interval16{
		{
			start:  uint16(),
			length: uint16( - 1 - ),
		},
	})
	* = *.union()
	return 
}

// remove the values in the range [firstOfRange,endx)
func ( *runContainer16) (,  int) container {
	if  >  {
		panic(fmt.Sprintf("request to iremove empty set [%v, %v),"+
			" nothing to do.", , ))
	}
	// empty removal
	if  ==  {
		return 
	}
	 := newInterval16Range(uint16(), uint16(-1))
	.isubtract()
	return 
}

// not flip the values in the range [firstOfRange,endx)
func ( *runContainer16) (,  int) container {
	if  >  {
		panic(fmt.Sprintf("invalid %v = endx > firstOfRange = %v", , ))
	}

	return .Not(, )
}

// Not flips the values in the range [firstOfRange,endx).
// This is not inplace. Only the returned value has the flipped bits.
//
// Currently implemented as (!A intersect B) union (A minus B),
// where A is rc, and B is the supplied [firstOfRange, endx) interval.
//
// TODO(time optimization): convert this to a single pass
// algorithm by copying AndNotRunContainer16() and modifying it.
// Current routine is correct but
// makes 2 more passes through the arrays than should be
// strictly necessary. Measure both ways though--this may not matter.
func ( *runContainer16) (,  int) *runContainer16 {

	if  >  {
		panic(fmt.Sprintf("invalid %v = endx > firstOfRange == %v", , ))
	}

	if  >=  {
		return .Clone()
	}

	 := 
	// algo:
	// (!A intersect B) union (A minus B)

	 := .invert()

	 := []interval16{newInterval16Range(uint16(), uint16(-1))}
	 := newRunContainer16TakeOwnership()

	 := .intersect()

	 := .AndNotRunContainer16()

	 := .union()
	return 
}

// equals is now logical equals; it does not require the
// same underlying container type.
func ( *runContainer16) ( container) bool {
	,  := .(*runContainer16)

	if ! {
		// maybe value instead of pointer
		,  := .(*runContainer16)
		if  {
			 = 
			 = true
		}
	}
	if  {
		// Check if the containers are the same object.
		if  ==  {
			return true
		}

		if len(.iv) != len(.iv) {
			return false
		}

		for ,  := range .iv {
			if  != .iv[] {
				return false
			}
		}
		return true
	}

	// use generic comparison
	if .getCardinality() != .getCardinality() {
		return false
	}
	 := .getShortIterator()
	 := .getShortIterator()

	//k := 0
	for .hasNext() {
		if .next() != .next() {
			return false
		}
		//k++
	}
	return true
}

func ( *runContainer16) ( uint16) container {
	.Add()
	return 
}

func ( *runContainer16) ( uint16) ( bool) {
	return .Add()
}

func ( *runContainer16) ( uint16) container {
	.removeKey()
	return 
}

func ( *runContainer16) ( uint16) bool {
	return .removeKey()
}

func ( *runContainer16) ( container) container {
	if .isFull() {
		return .clone()
	}
	switch c := .(type) {
	case *runContainer16:
		return .union()
	case *arrayContainer:
		return .orArray()
	case *bitmapContainer:
		return .orBitmapContainer()
	}
	panic("unsupported container type")
}

func ( *runContainer16) ( container) int {
	switch c := .(type) {
	case *runContainer16:
		return int(.unionCardinality())
	case *arrayContainer:
		return .orArrayCardinality()
	case *bitmapContainer:
		return .orBitmapContainerCardinality()
	}
	panic("unsupported container type")
}

// orBitmapContainer finds the union of rc and bc.
func ( *runContainer16) ( *bitmapContainer) container {
	 := newBitmapContainerFromRun()
	return .iorBitmap()
}

func ( *runContainer16) ( *bitmapContainer) int {
	 := 0
	for  := range .iv {
		 += .getCardinalityInRange(uint(.iv[].start), uint(.iv[].last())+1)
	}
	//bc.computeCardinality()
	return 
}

func ( *runContainer16) ( *bitmapContainer) int {
	return .getCardinality() + .getCardinality() - .andBitmapContainerCardinality()
}

// orArray finds the union of rc and ac.
func ( *runContainer16) ( *arrayContainer) container {
	if .isEmpty() {
		return .clone()
	}
	if .isEmpty() {
		return .clone()
	}
	,  := runArrayUnionToRuns(, )
	 := newRunContainer16TakeOwnership()
	if len() >= 2048 &&  >= arrayDefaultMaxSize {
		return newBitmapContainerFromRun()
	}
	if len()*2 > 1+int() {
		return .toArrayContainer()
	}
	return 
}

// orArray finds the union of rc and ac.
func ( *runContainer16) ( *arrayContainer) int {
	return .getCardinality() + .getCardinality() - .andArrayCardinality()
}

func ( *runContainer16) ( container) container {
	if .isFull() {
		return 
	}
	switch c := .(type) {
	case *runContainer16:
		return .inplaceUnion()
	case *arrayContainer:
		return .iorArray()
	case *bitmapContainer:
		return .iorBitmapContainer()
	}
	panic("unsupported container type")
}

func ( *runContainer16) ( *runContainer16) container {
	for ,  := range .iv {
		 := int(.last())
		for  := int(.start);  <= ; ++ {
			.Add(uint16())
		}
	}
	return 
}

func ( *runContainer16) ( *bitmapContainer) container {

	 := .getShortIterator()
	for .hasNext() {
		.Add(.next())
	}
	return 
}

func ( *runContainer16) ( *arrayContainer) container {
	if .isEmpty() {
		return .clone()
	}
	if .isEmpty() {
		return 
	}
	var  uint16
	//TODO: perform the union algorithm in-place using rc.iv
	// this can be done with methods like the in-place array container union
	// but maybe lazily moving the remaining elements back.
	.iv,  = runArrayUnionToRuns(, )
	if len(.iv) >= 2048 &&  >= arrayDefaultMaxSize {
		return newBitmapContainerFromRun()
	}
	if len(.iv)*2 > 1+int() {
		return .toArrayContainer()
	}
	return 
}

func runArrayUnionToRuns( *runContainer16,  *arrayContainer) ([]interval16, uint16) {
	 := 0
	 := 0
	 := len(.content)
	 := len(.iv)
	 := make([]interval16, 0, len(.iv))
	// have to find the first range
	// options are
	// 1. from array container
	// 2. from run container
	var  interval16
	var  uint16
	if .content[0] < .iv[0].start {
		.start = .content[0]
		.length = 0
		++
	} else {
		.start = .iv[0].start
		.length = .iv[0].length
		++
	}

	for  <  ||  <  {
		if  <  {
			 := .content[]
			if  <= .start+.length {
				++
				continue
			}
			if .last() < MaxUint16 && .last()+1 ==  {
				.length++
				++
				continue
			}
		}
		if  <  {
			 := .iv[]
			if .start <= .last() || .start > 0 && .start-1 == .last() {
				++
				if .last() < .last() {
					.length = .last() - .start
				}
				continue
			}
		}
		 += .length + 1
		 = append(, )
		if  ==  ||  <  && .content[] < .iv[].start {
			.start = .content[]
			.length = 0
			++
		} else {
			 = .iv[]
			++
		}
	}
	 += .length
	 = append(, )

	return , 
}

// lazyIOR is described (not yet implemented) in
// this nice note from @lemire on
// https://github.com/RoaringBitmap/roaring/pull/70#issuecomment-263613737
//
// Description of lazyOR and lazyIOR from @lemire:
//
// Lazy functions are optional and can be simply
// wrapper around non-lazy functions.
//
// The idea of "laziness" is as follows. It is
// inspired by the concept of lazy evaluation
// you might be familiar with (functional programming
// and all that). So a roaring bitmap is
// such that all its containers are, in some
// sense, chosen to use as little memory as
// possible. This is nice. Also, all bitsets
// are "cardinality aware" so that you can do
// fast rank/select queries, or query the
// cardinality of the whole bitmap... very fast,
// without latency.
//
// However, imagine that you are aggregating 100
// bitmaps together. So you OR the first two, then OR
// that with the third one and so forth. Clearly,
// intermediate bitmaps don't need to be as
// compressed as possible, right? They can be
// in a "dirty state". You only need the end
// result to be in a nice state... which you
// can achieve by calling repairAfterLazy at the end.
//
// The Java/C code does something special for
// the in-place lazy OR runs. The idea is that
// instead of taking two run containers and
// generating a new one, we actually try to
// do the computation in-place through a
// technique invented by @gssiyankai (pinging him!).
// What you do is you check whether the host
// run container has lots of extra capacity.
// If it does, you move its data at the end of
// the backing array, and then you write
// the answer at the beginning. What this
// trick does is minimize memory allocations.
func ( *runContainer16) ( container) container {
	// not lazy at the moment
	return .ior()
}

// lazyOR is described above in lazyIOR.
func ( *runContainer16) ( container) container {
	// not lazy at the moment
	return .or()
}

func ( *runContainer16) ( container) bool {
	// TODO: optimize by doing inplace/less allocation
	 := .and()
	return !.isEmpty()
}

func ( *runContainer16) ( container) container {
	switch c := .(type) {
	case *arrayContainer:
		return .xorArray()
	case *bitmapContainer:
		return .xorBitmap()
	case *runContainer16:
		return .xorRunContainer16()
	}
	panic("unsupported container type")
}

func ( *runContainer16) ( container) container {
	switch c := .(type) {
	case *arrayContainer:
		return .iandNotArray()
	case *bitmapContainer:
		return .iandNotBitmap()
	case *runContainer16:
		return .iandNotRunContainer16()
	}
	panic("unsupported container type")
}

// flip the values in the range [firstOfRange,endx)
func ( *runContainer16) (,  int) container {
	if  >  {
		panic(fmt.Sprintf("invalid %v = endx > firstOfRange = %v", , ))
	}
	if  >  {
		return 
	}
	// TODO: minimize copies, do it all inplace; not() makes a copy.
	 = .Not(, )
	return 
}

func ( *runContainer16) ( uint16) int {
	 := int(len(.iv))
	 := int()
	, ,  := .search()
	if  < 0 {
		return 0
	}
	if ! &&  == -1 {
		return .getCardinality()
	}
	var  int
	if ! {
		for  := int(0);  <= ; ++ {
			 += .iv[].runlen()
		}
		return int()
	}
	for  := int(0);  < ; ++ {
		 += .iv[].runlen()
	}
	 += int(-.iv[].start) + 1
	return int()
}

func ( *runContainer16) ( uint16) int {
	var  int
	for  := range .iv {
		 :=  + .iv[].runlen()
		if  > int() {
			return int(int(.iv[].start) + (int() - ))
		}
		 = 
	}
	panic("cannot select x")
}

func ( *runContainer16) ( *runContainer16) container {
	return .AndNotRunContainer16()
}

func ( *runContainer16) ( *arrayContainer) container {
	 := .toBitmapContainer()
	 := .toBitmapContainer()
	return .andNotBitmap()
}

func ( *runContainer16) ( *bitmapContainer) container {
	 := .toBitmapContainer()
	return .andNotBitmap()
}

func ( *runContainer16) () *bitmapContainer {
	 := newBitmapContainer()
	for  := range .iv {
		.iaddRange(int(.iv[].start), int(.iv[].last())+1)
	}
	.computeCardinality()
	return 
}

func ( *runContainer16) ( *runContainer16) container {
	 := .toBitmapContainer()
	 := .toBitmapContainer()
	.iandNotBitmapSurely()
	// TODO: check size and optimize the return value
	// TODO: is inplace modification really required? If not, elide the copy.
	 := newRunContainer16FromBitmapContainer()
	* = *
	return 
}

func ( *runContainer16) ( *arrayContainer) container {
	 := .toBitmapContainer()
	 := .toBitmapContainer()
	.iandNotBitmapSurely()
	// TODO: check size and optimize the return value
	// TODO: is inplace modification really required? If not, elide the copy.
	 := newRunContainer16FromBitmapContainer()
	* = *
	return 
}

func ( *runContainer16) ( *bitmapContainer) container {
	 := .toBitmapContainer()
	.iandNotBitmapSurely()
	// TODO: check size and optimize the return value
	// TODO: is inplace modification really required? If not, elide the copy.
	 := newRunContainer16FromBitmapContainer()
	* = *
	return 
}

func ( *runContainer16) ( *runContainer16) container {
	 := .toBitmapContainer()
	 := .toBitmapContainer()
	return .xorBitmap()
}

func ( *runContainer16) ( *arrayContainer) container {
	 := .toBitmapContainer()
	 := .toBitmapContainer()
	return .xorBitmap()
}

func ( *runContainer16) ( *bitmapContainer) container {
	 := .toBitmapContainer()
	return .xorBitmap()
}

// convert to bitmap or array *if needed*
func ( *runContainer16) () container {
	 := .getSizeInBytes()
	 := bitmapContainerSizeInBytes()
	 := .getCardinality()
	 := arrayContainerSizeInBytes()
	if  <= minOfInt(, ) {
		return 
	}
	if  <= arrayDefaultMaxSize {
		return .toArrayContainer()
	}
	 := newBitmapContainerFromRun()
	return 
}

func ( *runContainer16) () *arrayContainer {
	 := newArrayContainer()
	for  := range .iv {
		.iaddRange(int(.iv[].start), int(.iv[].last())+1)
	}
	return 
}

func newRunContainer16FromContainer( container) *runContainer16 {

	switch x := .(type) {
	case *runContainer16:
		return .Clone()
	case *arrayContainer:
		return newRunContainer16FromArray()
	case *bitmapContainer:
		return newRunContainer16FromBitmapContainer()
	}
	panic("unsupported container type")
}

// And finds the intersection of rc and b.
func ( *runContainer16) ( *Bitmap) *Bitmap {
	 := NewBitmap()
	for ,  := range .iv {
		 := .last()
		for  := .start;  <= ; ++ {
			if .Contains(uint32()) {
				.Add(uint32())
			}
		}
	}
	return 
}

// Xor returns the exclusive-or of rc and b.
func ( *runContainer16) ( *Bitmap) *Bitmap {
	 := .Clone()
	for ,  := range .iv {
		 := .last()
		for  := .start;  <= ; ++ {
			 := uint32()
			if .Contains() {
				.RemoveRange(uint64(), uint64(+1))
			} else {
				.Add()
			}
		}
	}
	return 
}

// Or returns the union of rc and b.
func ( *runContainer16) ( *Bitmap) *Bitmap {
	 := .Clone()
	for ,  := range .iv {
		 := .last()
		for  := .start;  <= ; ++ {
			.Add(uint32())
		}
	}
	return 
}

// serializedSizeInBytes returns the number of bytes of memory
// required by this runContainer16. This is for the
// Roaring format, as specified https://github.com/RoaringBitmap/RoaringFormatSpec/
func ( *runContainer16) () int {
	// number of runs in one uint16, then each run
	// needs two more uint16
	return 2 + len(.iv)*4
}

func ( *runContainer16) ( uint16) (container, container) {
	var ,  *runContainer16

	if len(.iv) == 0 {
		return nil, nil
	}

	 := uint32(.iv[0].start) + uint32()
	if highbits() == 0 {
		// Some elements will fall into low part, allocate a container.
		// Checking the first one is enough because they are ordered.
		 = newRunContainer16()
	}
	 := uint32(.iv[len(.iv)-1].start)
	 += uint32(.iv[len(.iv)-1].length)
	 += uint32()
	if highbits() > 0 {
		// Some elements will fall into high part, allocate a container.
		// Checking the last one is enough because they are ordered.
		 = newRunContainer16()
	}

	for ,  := range .iv {
		 := int(.start) + int()
		 := int() + int(.length)
		if  <= 0xffff {
			if  <= 0xffff {
				.iv = append(.iv, interval16{uint16(), .length})
			} else {
				.iv = append(.iv, interval16{uint16(), uint16(0xffff - )})
				.iv = append(.iv, interval16{uint16(0), uint16( & 0xffff)})
			}
		} else {
			.iv = append(.iv, interval16{uint16( & 0xffff), .length})
		}
	}

	// Ensure proper nil interface.
	if  == nil {
		return nil, 
	}
	if  == nil {
		return , nil
	}

	return , 
}